package leetcode_ago.bin_tree;

/**
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向
 * 思路：树进行中序遍历：中序遍历出来的链表节点值顺序排列，此时的遍历就是一个转换操作，将左子树转换为一个双向链表
 * 通过子函数传入treeToDoublyList(root.left)就转了：这个方法干的事情就是将树转换为双向链表
 * 此时leftHead就是左链表的头节点
 * 根节点的处理：左子树尾节点的next(也就是尾节点的right)==root，根节点的前驱要连接左子树的尾节点:root.prev(也就是left)==leftTail
 */
public class NumJZ36_TreeToDoubleLink{
        class Node {
                public int val;
                public Node left;
                public Node right;

                public Node() {}

                public Node(int _val) {
                        val = _val;
                }

                public Node(int _val,Node _left,Node _right) {
                        val = _val;
                        left = _left;
                        right = _right;
                }
        };
        //prev指向链表root节点的前驱节点
        Node prev;
        //链表头节点
        Node head;

        public Node treeToDoublyList(Node root) {
                if(root==null){
                        return null;
                }
                //构建有序双向链表
                treeToDoublyListHelper(root);
                //头节点尾节点连接
                //head指向头节点，prev指向尾节点
                head.left=prev;
                prev.right=head;
                return head;
        }
        //有序：通过中序遍历实现
        //这个方法的用途就是把二叉树转为有序双向链表
        private void treeToDoublyListHelper(Node root) {
                if(root==null){
                        return;
                }
                //处理左子树转为有序双向链表
                treeToDoublyListHelper(root.left);
                //处理根节点的连接
                if(prev!=null){
                        //prev的下一位是待处理的根节点，但不是头节点
                        //连接
                        prev.right=root;
                        root.left=prev;
                        //prev往后走一位
                        prev=root;
                }else{
                        //prev的下一位即root就是头节点
                        head=root;
                        prev=head;
                }
                //处理右子树转为有序双向链表
                treeToDoublyList(root.right);
        }

}
